package com.lims.algorithm.algset.heap;

import java.util.ArrayList;
import java.util.List;

/**
 * <功能简述>二叉堆
 *
 * @author lims
 * @date 2020-07-21 16:38
 */
public class MaxHeap<T extends Comparable<T>> {
    /**
     * 队列（动态数组实现）
     */
    private List<T> mHeap;

    public MaxHeap() {
        this.mHeap = new ArrayList<>();
    }

    /**
     * 将data插入
     */
    public void insert(T data) {
        int size = mHeap.size();

        mHeap.add(data);
        fixUp(size);
    }

    /**
     * 最大堆的向上调整算法(从start开始向上直到0，调整堆)
     * 注：数组实现的堆中，第N个节点的左孩子的索引值是(2N+1)，右孩子的索引是(2N+2)。
     *
     * @param start 被上调节点的起始位置(一般为数组中最后一个元素的索引)
     */
    protected void fixUp(int start) {
        int c = start;
        // 父结点的索引下标
        int p = (c - 1) / 2;
        T tmp = mHeap.get(c);

        while (c > 0) {
            int cmp = mHeap.get(p).compareTo(tmp);
            if (cmp > 0) {
                break;
            } else {
                mHeap.set(c, mHeap.get(p));
                c = p;
                p = (c - 1) / 2;
            }
        }
        mHeap.set(c, tmp);
    }

    /**
     * @param data 要删除数据
     * @return 0, 成功 1，失败
     */
    public int remove(T data) {
        if (mHeap.isEmpty()) {
            return -1;
        }
        // 在数组中索引
        int index = mHeap.indexOf(data);
        if (index == -1) {
            return -1;
        }
        int size = mHeap.size();
        // 用最后一个替换删除
        mHeap.set(index, mHeap.get(size - 1));
        // 删除最后一个
        mHeap.remove(size - 1);

        //向下调整 从index开始向下调整为最大堆
        if (mHeap.size() > 1) {
            fixDown(index, mHeap.size() - 1);
        }
        return 0;
    }

    /**
     * 最大堆的向下调整算法
     * 注：数组实现的堆中，第N个节点的左孩子的索引值是(2N+1)，右孩子的索引是(2N+2)。
     *
     * @param start -- 被下调节点的起始位置(一般为0，表示从第1个开始)
     * @param end   -- 截至范围(一般为数组中最后一个元素的索引)
     */
    protected void fixDown(int start, int end) {
        int c = start;
        // left左孩子位置
        int l = 2 * c + 1;
        T tmp = mHeap.get(c);
        while (l <= end) {
            int cmp;
            // 边界 c只有左子l，没有右子l+1
            if (l + 1 <= end) {
                // l为左孩子，所以不可能l==end
                cmp = mHeap.get(l).compareTo(mHeap.get(l + 1));
                // l左孩子 l+1 右孩子
                if (l < end && cmp < 0) {
                    // 选择左右孩子中的最大者
                    l++;
                }
            }

            cmp = tmp.compareTo(mHeap.get(l));
            if (cmp >= 0) {
                break;
            } else {
                mHeap.set(c, mHeap.get(l));
                c = l;
                l = 2 * c + 1;
            }
        }
        mHeap.set(c, tmp);
    }

    @Override
    public String toString() {
        return mHeap.toString();
    }

    /********************************************************/

    public static void main(String[] args) {
        int a[] = {10, 40, 30, 60, 90, 70, 20, 50, 80};
        MaxHeap<Integer> maxHeap = new MaxHeap<>();

        System.out.println("== 依次添加： ");
        for (int i : a) {
            System.out.printf("%d ", i);
            maxHeap.insert(i);
        }
        System.out.printf("\n ==最大堆: %s", maxHeap);

        System.out.println("添加元素：85 ");
        maxHeap.insert(85);
        System.out.printf("\n ==最大堆: %s", maxHeap);

        maxHeap.insert(20);
        maxHeap.insert(21);
        maxHeap.insert(22);
        maxHeap.insert(23);
        maxHeap.insert(24);
        maxHeap.insert(25);

        System.out.printf("\n ==最大堆: %s", maxHeap);

        maxHeap.remove(85);
        System.out.printf("\n ==最大堆: %s", maxHeap);
    }
}
